<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.png?v=5.1.4">


  <link rel="mask-icon" href="/images/favicon.png?v=5.1.4" color="#222">





  <meta name="keywords" content="编译原理," />





  <link rel="alternate" href="/atom.xml" title="平步青云win" type="application/atom+xml" />






<meta name="description" content="编译原理学习笔记。">
<meta name="keywords" content="编译原理">
<meta property="og:type" content="article">
<meta property="og:title" content="编译原理">
<meta property="og:url" content="https://zxpgo.github.io/2020/04/17/编译原理/index.html">
<meta property="og:site_name" content="平步青云win">
<meta property="og:description" content="编译原理学习笔记。">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417203838.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417204255.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417211332.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200423233042.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200423233415.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200423234240.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425175333.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425180613.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181023.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181046.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181130.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181154.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425182647.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425184654.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425190317.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425190451.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508164608087.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200426102635.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200426103049.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508170439014.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508172924163.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508193632350.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508194456469.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508194714825.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508204704315.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508205232765.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508211147930.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508210838380.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508210850892.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509125120172.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509130042710.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509150955233.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509151248177.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509152425899.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509152904280.png">
<meta property="og:image" content="c:/Program%20Files/Typora/upload/image-20200510095240335.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510100652361.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510100741694.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510101135283.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510101814026.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510104154071.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510104207824.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510104259359.png">
<meta property="og:image" content="c:/Program%20Files/Typora/upload/image-20200510104810148.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510105240112.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510114605955.png">
<meta property="og:image" content="c:/Program%20Files/Typora/upload/image-20200510115300043.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510115550338.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510115650316.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510120629577.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510120727145.png">
<meta property="og:image" content="c:/Program%20Files/Typora/upload/image-20200510142715112.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510142819794.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510143819079.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510144156287.png">
<meta property="og:image" content="c:/Program%20Files/Typora/upload/image-20200510144343503.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510144826925.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510145052277.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510145346504.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510150629931.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151001684.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151651151.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151633396.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151805416.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510152057713.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510152324062.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510152409034.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510155556458.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510160542843.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511100600620.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511100739781.png">
<meta property="og:image" content="c:/Program%20Files/Typora/upload/image-20200511101005809.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511102001166.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511102635190.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511103023304.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511104328127.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511125006810.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511131205695.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511131651613.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511132902835.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511133109864.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511143057864.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511143323782.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511143939647.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511144340728.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511145557054.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511145911875.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511152217270.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511152339433.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511152852447.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161018159.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161037267.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161120275.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161238525.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161331126.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511153452496.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511162316794.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511162703912.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511162806324.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511163607090.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090031072.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090042758.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090217925.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090743083.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091024575.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091057805.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091514495.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091819178.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091057805.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514143755112.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514144217756.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514144406272.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514144558923.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514152143495.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514161142318.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514153425448.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514153806088.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518100542173.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518100655214.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518100916852.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518101430032.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518103311338.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518110525787.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518110742089.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518133849440.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518134001088.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102004908.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102350471.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102513062.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102915480.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521104402066.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521142101208.png">
<meta property="og:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521142610030.png">
<meta property="og:updated_time" content="2020-05-21T06:30:16.236Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="编译原理">
<meta name="twitter:description" content="编译原理学习笔记。">
<meta name="twitter:image" content="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417203838.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":10,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: 'PAO8LM7QB1',
      apiKey: '',
      indexName: 'Blog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://zxpgo.github.io/2020/04/17/编译原理/"/>





  <title>编译原理 | 平步青云win</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?7a4517a3ce6d7c50203655d056f01ac3";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">平步青云win</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description"></h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-随笔">
          <a href="/sui" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            随笔
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
			
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://zxpgo.github.io/2020/04/17/编译原理/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="zxp">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平步青云win">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">编译原理</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2020-04-17T17:24:24+08:00">
                2020-04-17
              </time>
            

            

            
          </span>

          

          
            
          

          
          
             <span id="/2020/04/17/编译原理/" class="leancloud_visitors" data-flag-title="编译原理">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">阅读次数&#58;</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        <p>编译原理学习笔记。<a id="more"></a></p>
<h1 id="绪论"><a href="#绪论" class="headerlink" title="绪论"></a>绪论</h1><h2 id="什么是编译"><a href="#什么是编译" class="headerlink" title="什么是编译"></a>什么是编译</h2><p>程序设计语言</p>
<ul>
<li>机器语言：可以被计算机直接理解 </li>
<li>汇编语言：引入助记符<ul>
<li>依赖于特定机器，非计算机专业人员使用受限制</li>
<li>编写效率依然很低</li>
</ul>
</li>
<li>高级语言：类似于数学定义或自然语言的简洁形式<ul>
<li>接近人类表达习惯</li>
<li>不依赖于特定机器</li>
<li>编写效率高</li>
</ul>
</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">C706 <span class="number">0000</span> <span class="number">00002</span>  <span class="comment">//机器语言</span></span><br><span class="line">MOV X, <span class="number">2</span>         <span class="comment">//汇编语言</span></span><br><span class="line">x = <span class="number">2</span>            <span class="comment">//高级语言</span></span><br></pre></td></tr></table></figure>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417203838.png" alt=""></p>
<p>编译：</p>
<ul>
<li>高级语言-&gt;汇编语言</li>
<li>讲高级语言(源语言)翻译成汇编语言或机器语言(目标语言)的过程</li>
</ul>
<h2 id="源文件到目标机器码的过程："><a href="#源文件到目标机器码的过程：" class="headerlink" title="源文件到目标机器码的过程："></a>源文件到目标机器码的过程：</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417204255.png" alt=""></p>
<p>预处理器：</p>
<ul>
<li>负责把存储在不同文件中的源程序聚合在一起</li>
<li>把被称为宏的缩写语言装换为原始语句<br>编译器</li>
<li>将源代码编译成汇编代码<br>汇编器：</li>
<li>将汇编代码编译成可重定位的机器代码</li>
<li>可重定位：表示在内存中存放的起始位置L不是固定的<br>加载器：</li>
<li>修改可重定位地址：将修改后的指令和数据放到内存中适当的位置</li>
<li>起始地址+相对地址=绝对地址<br>链接器：</li>
<li>大型程序经常被分割成多个部门被编译，所以可重定位的机器代码可以与其他可重定位目标程序或库文件进行链接生成可执行代码</li>
<li>解决外部内存地址问题</li>
</ul>
<h2 id="编译系统结构"><a href="#编译系统结构" class="headerlink" title="编译系统结构"></a>编译系统结构</h2><p>编译器的输入是高级语言程序，输出是汇编语言程序/机器语言程序。<br><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200417211332.png" alt=""></p>
<p>分析部分：与源语言相关</p>
<ul>
<li><p>词法分析：确定各个单词的词性或词类</p>
</li>
<li><p>语法分析：识别句子中的各类短语，从而确定句子结构</p>
</li>
<li><p>语义分析：根据句子结构分析出各个短语在句子中充当什么成分，从而确定各个名字性成分同谓语动词之间的关系</p>
</li>
<li><p>中间代码生成：语义分析的结果通常直接当做中间代码生成的结果，这两个阶段通常一起实现。</p>
</li>
</ul>
<p>综合部门：与目标语言相关</p>
<ul>
<li><p>目标代码生成：</p>
</li>
<li><p>代码优化：</p>
</li>
</ul>
<p>语法制导翻译：这种情况下，语法分析，语义分析和中间代码生成放在一起实现。</p>
<h3 id="词法分析"><a href="#词法分析" class="headerlink" title="词法分析"></a>词法分析</h3><p>从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(token)形式。token是一个二元组，&lt;种别码，属性值&gt;</p>
<p>种别码：</p>
<ul>
<li><p>关键字：if,else。一词一码</p>
</li>
<li><p>标识符：变量名，数组名，函数名。多词一码</p>
</li>
<li>常量：整形，浮点型，字符型，布尔型。一型一码</li>
<li>运算符：算术，关系，逻辑。一词一码或一型一码</li>
<li>界限符：括号，分号。一词一码</li>
</ul>
<p>对于多词一码或者一型一码，通过属性值来区别。</p>
<h3 id="语法分析"><a href="#语法分析" class="headerlink" title="语法分析"></a>语法分析</h3><p>从词法分析输出的token序列中识别出各类短语，并构造语法分析树。语法分析树描述了句子的语法结构。</p>
<ul>
<li>赋值语句的分析树</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">position       =    initial        +   rate      *       <span class="number">60</span>   ;</span><br><span class="line">&lt;id, position&gt; &lt;=&gt;   &lt;id, initial&gt; &lt;+&gt; &lt;id,rate&gt; &lt;*&gt;  &lt;num,<span class="number">60</span>&gt;&lt;;&gt;</span><br></pre></td></tr></table></figure>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200423233042.png" alt=""></p>
<ul>
<li>变量声明语句的分析树</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200423233415.png" alt=""></p>
<h3 id="语义分析"><a href="#语义分析" class="headerlink" title="语义分析"></a>语义分析</h3><p>主要任务：</p>
<ul>
<li><p>收集标识符的属性信息</p>
<ul>
<li>种属：简单变量，复合变量(数组)，过程</li>
<li>类型：字符型，整型</li>
<li>存储位置、长度</li>
<li>变量的值</li>
<li>变量的作用域</li>
<li>参数和返回值信息：对于过程(函数)，参数个数等</li>
</ul>
<p>标识符属性存储在符号表中，每个标识符对应符号表中的一行，每一列对应标识符的属性。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200423234240.png" alt=""></p>
</li>
</ul>
<p>字符串表用来存储标识符和字符常量。Name字段被分割成两个部分，第一个部分用来存储字符串的其实位置，第二个部分用来存储字符串的长度。</p>
<ul>
<li><p>语义检查</p>
<ul>
<li><p>变量或过程未经声明就使用</p>
</li>
<li><p>变量或过程名重复声明</p>
</li>
<li><p>运算分量类型不匹配</p>
</li>
<li><p>操作符与操作数之间的类型不匹配，比如</p>
<ul>
<li>数组下标不是整数</li>
<li>对非数组变量使用数组访问操作符</li>
<li>对非过程名使用过程调用操作符</li>
<li>过程调用的参数类型或数目不匹配</li>
<li>函数返回类型有误</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="中间代码生成"><a href="#中间代码生成" class="headerlink" title="中间代码生成"></a>中间代码生成</h3><p>中间表示形式：</p>
<ul>
<li>三地址码<ul>
<li>三地址码由类似于汇编的指令序列组成</li>
<li>每个指令最多有三个操作数</li>
<li>三地址指令序列唯一确定了运算完成的顺序</li>
<li>三地址指令的表示<ul>
<li>四元式: (op,y,z,x)，op表示操作符，x表示目标数，y，z表示操作数</li>
<li>三元式</li>
<li>间接三元式</li>
</ul>
</li>
</ul>
</li>
<li>语法结构树/语法树</li>
</ul>
<h3 id="目标代码生成"><a href="#目标代码生成" class="headerlink" title="目标代码生成"></a>目标代码生成</h3><p>目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言。</p>
<p>目标代码生成的一个重要任务是为程序使用的变量合理分配寄存器。</p>
<h3 id="代码优化"><a href="#代码优化" class="headerlink" title="代码优化"></a>代码优化</h3><p>为改进代码所进行的等级程序变换，使其运行得更快一些，占用空间更少一些，或者二者兼顾。</p>
<p>代码优化分为：</p>
<ul>
<li>机器无关代码优化：中间代码层面优化</li>
<li>机器相关代码优化：目标代码层面优化</li>
</ul>
<p>优化的方面：</p>
<ul>
<li>自动识别代码中的重复运算或冗余运算，并删除</li>
<li>将代价较高的运算替换成代价较少的运算</li>
</ul>
<h1 id="语言及其文法"><a href="#语言及其文法" class="headerlink" title="语言及其文法"></a>语言及其文法</h1><h2 id="基本概念"><a href="#基本概念" class="headerlink" title="基本概念"></a>基本概念</h2><h3 id="字母表"><a href="#字母表" class="headerlink" title="字母表"></a>字母表</h3><p>是一个有穷符号集合。</p>
<p>符号：包括字母，数字，标点符号等</p>
<p>字母表上的运算：</p>
<ul>
<li>乘积</li>
<li>n次幂</li>
<li>正闭包</li>
<li>克林闭包：正闭包加上空串</li>
</ul>
<h3 id="串"><a href="#串" class="headerlink" title="串"></a>串</h3><p>串是字母表中符号的一个有穷序列。</p>
<p>串s的长度，通常记作<code>|s|</code>，指s中符号的个数。比如<code>|abc|=3</code></p>
<p>空串的长度为0的串，用$\epsilon$表示，$|\epsilon|=0$</p>
<p>串上的运算：</p>
<ul>
<li>连接</li>
</ul>
<p>x和y是串，x和y的连接，是把y附加到x后面而形成的串，记作xy</p>
<p>例如x=dog, y = house，那么xy=doghouse</p>
<p>空串是单元位。</p>
<ul>
<li><p>幂</p>
<p>$s^1= s^0 s = \epsilon s= s, s^2 = ss$</p>
</li>
</ul>
<h2 id="文法定义"><a href="#文法定义" class="headerlink" title="文法定义"></a>文法定义</h2><p>文法的形式化定义：$G=(V_T,V_N,P,S)$</p>
<p>$V_T$：终结符集合</p>
<p>终结符：是文法所定义的语言的基本符号，有时也称token。</p>
<p>例如：$V_T={apple,boy,eat,little }$</p>
<p>$V_N$：非终结符集合</p>
<p>非终结符：是用来表示语法成分的符号，有时也称为“语法变量”</p>
<p>例如：$V_N={&lt;句子&gt;,&lt;名词短语&gt;,&lt;动词短语&gt;,&lt;名词&gt; …}$</p>
<p>注意：</p>
<ul>
<li>终结符集合和非终结符集合是不相交的</li>
<li>终结符集合和非终结符集合并集为文法符号集</li>
</ul>
<p>$P$：产生式集合</p>
<p>产生式：描述了将终结符和非终结符组合成串的方法，产生式的一般形式为：$\alpha \Rightarrow  \beta$ </p>
<p>读作：$\alpha$定义为$\beta$</p>
<p>$S$：开始符号</p>
<p>$S \in V_N$。开始符号：表示的是该文法中最大的语法成分。</p>
<p>例如：$S=&lt;句子&gt;$</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425175333.png" alt=""></p>
<p>产生式的简写：</p>
<p>对于有相同左部的$\alpha$的产生式：<br>$$<br>\alpha \Rightarrow \beta_1  \space\space \alpha \Rightarrow \beta_2 \space…\space \alpha \Rightarrow \beta_n<br>$$<br>可以简记为：<br>$$<br>\alpha \Rightarrow \beta_1 | \beta_2 | …|\beta_n<br>$$<br>例如：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425180613.png" alt=""> </p>
<p>符号约定：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181023.png" alt=""></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181046.png" alt=""></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181130.png" alt=""></p>
<p>总结：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425181154.png" alt=""></p>
<h2 id="语言的定义"><a href="#语言的定义" class="headerlink" title="语言的定义"></a>语言的定义</h2><h3 id="推导"><a href="#推导" class="headerlink" title="推导"></a>推导</h3><p>直接推导就是用产生式的右部替换产生式的左部。</p>
<p>比如：<br>$$<br>\alpha \Rightarrow \beta \<br>\gamma \alpha \delta \Rightarrow \gamma \beta \delta<br>$$<br>间接推导</p>
<p>比如：<br>$$<br>\alpha_0 \Rightarrow \alpha_1 \space \alpha_1 \Rightarrow \alpha_2 \space …. \space \alpha_{n-1} \Rightarrow \alpha_n \<br>\alpha_0 \Rightarrow^{n} \alpha_n<br>$$</p>
<h3 id="规约"><a href="#规约" class="headerlink" title="规约"></a>规约</h3><p>规约是推导的逆过程。</p>
<p>例如：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425182647.png" alt=""></p>
<p>有了文法(语言规则)，如何判断某一词串是否是该语言的句子：</p>
<ul>
<li>句子的推导：是否能够从文法推导出句子</li>
<li>句子的规约：从该句子是否可以规约到文法的开始符号</li>
</ul>
<h3 id="句型和句子"><a href="#句型和句子" class="headerlink" title="句型和句子"></a>句型和句子</h3><p>如果$S \Rightarrow^<em> \alpha, \alpha \in (V_T \cup V_N)^</em>$，则称$\alpha$是$G$的一个句型。$S$是句子的开始符号。</p>
<p>一个句型中既可以包含终结符，也可以包含非终结符，也可能是空串。</p>
<p>如果$S \Rightarrow^<em> w, w \in V_T^</em>$，则称$w$是$G$的一个句子。</p>
<p>句子是不包含非终结符的句型。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425184654.png" alt=""></p>
<h3 id="语言"><a href="#语言" class="headerlink" title="语言"></a>语言</h3><p>由文法$G$的开始符号$S$推导出的所有句子构成的集合称为文法$G$生成的语言，记为$L(G)$。</p>
<p>即$(G)={w | S \Rightarrow^<em> w, w \in V_T^</em>}$</p>
<p>例如：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425190317.png" alt=""></p>
<p>其他S表示字母数字串，即有字母开头的，字母和数字组成的字符串。即变成语言中的标识符。</p>
<h3 id="语言上的运算"><a href="#语言上的运算" class="headerlink" title="语言上的运算"></a>语言上的运算</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200425190451.png" alt=""></p>
<p>例如：</p>
<p>令$L={A,B…,Z,a,b,..,z},D={0,1,…,9}$。则$L(L \cup D)^<em>$表示的语言是标识符。注意，$</em>$表示生成的串。$*$表示闭包运算。</p>
<h2 id="文法分类"><a href="#文法分类" class="headerlink" title="文法分类"></a>文法分类</h2><p>Chomsky文法分类体系：</p>
<ul>
<li><p>0型文法</p>
<ul>
<li>无限制文法/短语结构文法</li>
<li>$\forall \alpha \Rightarrow \beta \in P$,$\alpha$中至少包含1个非终结符</li>
<li>由0型文法$G$生成的语言$L(G)$是0型语言</li>
</ul>
</li>
<li><p>1型文法</p>
<ul>
<li>又称上下文有关文法（CSG）</li>
<li>满足0型文法的基础上，$\forall \alpha \Rightarrow \beta \in P$,$|\alpha| \leq |\beta|$</li>
<li>产生式的一般形式：$\alpha_1 A \alpha_2 \Rightarrow \alpha_1 \beta \alpha_2, (\beta \neq \epsilon)$</li>
<li>CSG中不包含空产生式，即$ \epsilon $。证明：如果$\beta=\epsilon$，即$|\beta| =0$，而$\alpha$必须包含一个非终结符，所以$|\alpha| \geq 1$，与$|\beta|=0$矛盾。</li>
<li>由上下文有关文法产生的语言称为上下文有关语言(1型语言)。</li>
</ul>
</li>
<li><p>2型文法</p>
<ul>
<li>上下文无关文法(CFG)</li>
<li>$\forall \alpha \Rightarrow \beta \in P$,$\alpha \in V_N$</li>
<li>产生式的一般形式：$A \Rightarrow \beta$，$A$表示非终结符，即生成式的左部是一个非终结符，如下就是一个上下文无关文法的例子：</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508164608087.png" alt="image-20200508164608087"></p>
</li>
<li><p>3型文法</p>
<ul>
<li>又称正则文法(RG)<ul>
<li>右线性文法：$A \Rightarrow wB 或 A \Rightarrow w$，$A$表示非终结符，$w$表示终结符</li>
<li>左线性文法：$A \Rightarrow Bw 或 A \Rightarrow w$</li>
<li>左线性文法和右线性文法都称为正则文法</li>
</ul>
</li>
<li>由正则文法$G$生成的语言称为正则语言</li>
<li>正则文法能描述程序设计语言的多数单词</li>
</ul>
</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200426102635.png" alt=""></p>
<p>四种文法的关系：</p>
<ul>
<li>逐级限制</li>
<li>逐级包含</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/20200426103049.png" alt=""></p>
<p>3型文法，一定是2型文法；2型文法，一定是1型文法；1型文法，一定是0型文法。反过来则不成立。</p>
<h2 id="CFG-上下文无关文法-的分析树"><a href="#CFG-上下文无关文法-的分析树" class="headerlink" title="CFG(上下文无关文法)的分析树"></a>CFG(上下文无关文法)的分析树</h2><p>正则文法可以描述程序语言中大多数单词，但是其生成能力有限， 它几乎描述不了程序设计语言中的句子构造。而上下文无关文法可以描述大部分程序设计语言中的语法构造，也是被研究得最多的一种文法。</p>
<p>分析树的定义：</p>
<ul>
<li>根节点的标号为文法开始符号</li>
<li>内部节点表示对一个产生式$A \Rightarrow \beta$的应用，该节点的标号是此产生式左部$A$.该节点的子节点的标号从左到右构成了产生式的右部$\beta$</li>
<li>叶节点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串是这颗树的产出或边缘。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508170439014.png" alt="image-20200508170439014"></p>
<h3 id="分析树是推导的图形化表示"><a href="#分析树是推导的图形化表示" class="headerlink" title="分析树是推导的图形化表示"></a>分析树是推导的图形化表示</h3><p>给定一个推导$S \Rightarrow \alpha_1 \Rightarrow \alpha_2 …\Rightarrow \alpha_n$，对于推导过程中得到的每一个句型$\alpha_i$都可以构造出一个边缘为$a_i$的分析树。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508172924163.png" alt="image-20200508172924163"></p>
<h3 id="句型的-短语"><a href="#句型的-短语" class="headerlink" title="(句型的)短语"></a>(句型的)短语</h3><p>给定一个句型，其分析树中的每一颗子树的边缘称为该句型的一个短语。</p>
<p>如果子树只有父子两代结点，那么这颗子树的边缘称为该句型的一个直接短语(高度为2的子树的边缘)。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508193632350.png" alt="image-20200508193632350"></p>
<p>直接短语一定是某个产生式的右部。</p>
<p>但产生式的右部不一定是给定句型的直接短语。</p>
<h3 id="二义性文法"><a href="#二义性文法" class="headerlink" title="二义性文法"></a>二义性文法</h3><p>如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。</p>
<p>编译器希望不要遇到二义性，不然就无法执行。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508194456469.png" alt="image-20200508194456469"></p>
<p>上面的句型可以通过文法可以表示成两棵分析树。这是由于else可以跟第一个if匹配，也可以跟第二if匹配。</p>
<p>所以消除二义性的规则是：每个else和最近的尚未匹配的if匹配。如果有了这条规定，上面句型的分析树就是唯一的了。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508194714825.png" alt="image-20200508194714825"></p>
<p>对于任意一个上下文无关文法，不存在一个算法，判断它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。</p>
<p>满足：肯定无二义性</p>
<p>不满足：也未必就是有二义性。</p>
<h1 id="词法分析-1"><a href="#词法分析-1" class="headerlink" title="词法分析"></a>词法分析</h1><h2 id="正则表达式"><a href="#正则表达式" class="headerlink" title="正则表达式"></a>正则表达式</h2><p>语言$L={a}{a,b}^<em>({\epsilon} \cup ({.,}{a,b} {a,b}^</em>))$</p>
<p>正则表达式(RE)是一种用来描述 正则语言的紧凑的表示方法：</p>
<p>例如：$r=a(a|b)^<em>(\epsilon | (.|-)(a|b)(a|b)^</em>)$</p>
<p>正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式$r$定义(表示)一个语言，记为$L(r)$。这个语言也是根据$r$的子表达式所表示的语言递归定义的。</p>
<h3 id="定义"><a href="#定义" class="headerlink" title="定义"></a>定义</h3><p>$\epsilon$是一个RE，$L(\epsilon) = {\epsilon }$</p>
<p>如果$\alpha \in \sum$，则$\alpha$是一个RE，$L(\alpha) = {\alpha}$</p>
<p>如果$r$和$s$都是RE，表示的语言分别是$L(r)$和$L(s)$，则：</p>
<ul>
<li>$r|s$是一个RE，$L(r|s)=L(r) \cup L(s)$</li>
<li>$rs$是一个RE，$L(rs) = L(r)L(s)$</li>
<li>$r^<em>$是一个RE，$L(r^</em>)=(L(r))^*$</li>
<li>$(r)$是一个RE，$L((r))=L(r)$</li>
</ul>
<p>运算优先级：$*$、连接，|</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508204704315.png" alt="image-20200508204704315"></p>
<p>例子：</p>
<p>C语言中无符号整数的RE：</p>
<p>十进制整数的RE：$(0|…|9)(0|…|9)^*|0$</p>
<p>八进制整数的RE：$0(1|…|7)(0|…|7)^*$</p>
<h2 id="正则语言"><a href="#正则语言" class="headerlink" title="正则语言"></a>正则语言</h2><p>可以用RE定义的语言，叫做正则语言或正则集合。</p>
<p>RE满足的代数定律：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508205232765.png" alt="image-20200508205232765"></p>
<p>正则文法和正则表达式等级：</p>
<p>对于任何正则文法$G$，存在定义同一语言的正则表达式$r$。</p>
<p>对于任何正则表达式$r$，存在生成同一语言的正则文法$G$。</p>
<h2 id="正则"><a href="#正则" class="headerlink" title="正则"></a>正则</h2><p>正则定义具有如下形式的定义序列：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508211147930.png" alt="image-20200508211147930"></p>
<p>其中：</p>
<ul>
<li>每个$d_i$都是一个新符号，它们都不在序列字母表$\sum$中，而且各不相同</li>
<li>每个$r_i$是字母表$\sum \cup {d_1,d_2,…,d_{i-1}}$上的正则表达式</li>
</ul>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508210838380.png" alt="image-20200508210838380"></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200508210850892.png" alt="image-20200508210850892"></p>
<h2 id="有穷自动机-FA"><a href="#有穷自动机-FA" class="headerlink" title="有穷自动机(FA)"></a>有穷自动机(FA)</h2><p>有穷自动机有两位神经物理学家于1948年首先提出，是对一类处理系统简历的数学模式。</p>
<p>这类系统具有一系列<strong>离散的输入输出信息和有穷数目的内部状态</strong>（状态：概况了对过去输入信息处理的状况）。</p>
<p>系统只需要根据<strong>当前所处的状态和当前面临的输入信息</strong>就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。</p>
<p>FA的典型例子：</p>
<p>电梯控制装置：</p>
<ul>
<li>输入：顾客的乘梯需求(所要到达的层号)</li>
<li>状态：电梯所处的层数+运动方向</li>
<li>电梯控制装置并不需要记住先前全部的服务要求，只需要知道电梯当前所处的状态以及还没满足的所有服务请求。</li>
</ul>
<h3 id="FA模型"><a href="#FA模型" class="headerlink" title="FA模型"></a>FA模型</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509125120172.png" alt="image-20200509125120172"></p>
<p>FA由三部分组成：</p>
<ul>
<li>输入带：用来存储输入符号串</li>
<li>读头：从做向右逐个读取输入符号，不能修改(只读)，不能往返移动</li>
<li>有穷控制器：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一个状态</li>
</ul>
<h3 id="FA表示"><a href="#FA表示" class="headerlink" title="FA表示"></a>FA表示</h3><p>转换图：</p>
<ul>
<li>结点：FA的状态<ul>
<li>初始状态(开始状态)：只有一个，有start箭头指向</li>
<li>终止状态(接收状态)：可以有多个，用双圈表示</li>
</ul>
</li>
<li>带有标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509130042710.png" alt="image-20200509130042710"></p>
<h3 id="FA定义-接收-的语言"><a href="#FA定义-接收-的语言" class="headerlink" title="FA定义(接收)的语言"></a>FA定义(接收)的语言</h3><p>给定输入串$x$，如果存在一个对应于串$x$的从初始状态到某个终止状态的转换序列，则称串$x$被该FA接受。</p>
<p>由一个有穷自动机$M$接收的所有串构成的集合称为是该FA定义（或接收）的语言，记为$L(M)$</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509150955233.png" alt="image-20200509150955233"></p>
<h3 id="最长子串匹配原则"><a href="#最长子串匹配原则" class="headerlink" title="最长子串匹配原则"></a>最长子串匹配原则</h3><p>当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。</p>
<p>在到大某个终态之后，只要输入带上还有符号，DFA就继续前进，以便寻找尽可能长的匹配。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509151248177.png" alt="image-20200509151248177"></p>
<p>所以如果遇到&lt;=符号，就会匹配成小于等于；如果遇到++符号，就会匹配成自增符号。</p>
<h2 id="FA分类"><a href="#FA分类" class="headerlink" title="FA分类"></a>FA分类</h2><ul>
<li><p>确定的FA(DFA)</p>
</li>
<li><p>非确定的FA(NFA)</p>
</li>
</ul>
<h3 id="确定的有穷自动机-DFA"><a href="#确定的有穷自动机-DFA" class="headerlink" title="确定的有穷自动机(DFA)"></a>确定的有穷自动机(DFA)</h3><p>$$<br>M = (S, \sum, \delta, s_0, F)<br>$$</p>
<p>$S$：有穷状态集</p>
<p>$\sum$ ：输入字母表，即输入符号集合，假设$\epsilon$不是$\sum$中的元素</p>
<p>$\delta$：将$S \times \sum$映射到$S$的转换函数。$\forall s \in S, a \in \sum, \delta(s,a)$表示从状态$s$出发，沿着表示$a$的边所能到达的状态。</p>
<p>$s_0$：开始（或初始）状态，$s_0 \in S$</p>
<p>$F$：接受状态（或终止状态）集合，$F \subset S$</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509152425899.png" alt="image-20200509152425899"></p>
<p>$S = {0,1,2,3}$</p>
<p>$\sum = {a,b}$</p>
<p>$F={3}$</p>
<p>$s_0 = 0$ </p>
<p>$\delta$可以用转换表表示</p>
<h3 id="非确定的有穷自动机-NFA"><a href="#非确定的有穷自动机-NFA" class="headerlink" title="非确定的有穷自动机(NFA)"></a>非确定的有穷自动机(NFA)</h3><p>$$<br>M = (S, \sum, \delta, s_0, F)<br>$$</p>
<p>$S$：有穷状态集</p>
<p>$\sum$ ：输入字母表，即输入符号集合，假设$\epsilon$不是$\sum$中的元素</p>
<p>$\delta$：将$S \times \sum$映射到<strong>$2^S$</strong>的转换函数。$\forall s \in S, a \in \sum, \delta(s,a)$表示从状态$s$出发，沿着表示$a$的边所能到达的状态<strong>集合</strong>。</p>
<p>$s_0$：开始（或初始）状态，$s_0 \in S$</p>
<p>$F$：接受状态（或终止状态）集合，$F \subset </p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200509152904280.png" alt="image-20200509152904280"></p>
<p>$s_0 = 0$</p>
<p>$S= {0,1,2,3}$</p>
<p>$F={3}$</p>
<p>$\sum = {a, b}$</p>
<h3 id="DFS和NFA的等价性"><a href="#DFS和NFA的等价性" class="headerlink" title="DFS和NFA的等价性"></a>DFS和NFA的等价性</h3><p>对于任何NFA，存在识别同一语言的DFA。</p>
<p>对于任何DFA，存在识别同一语言的NFA。</p>
<p><img src="C:/Program%20Files/Typora/upload/image-20200510095240335.png" alt="image-20200510095240335"></p>
<h3 id="带有-epsilon-边的NFA"><a href="#带有-epsilon-边的NFA" class="headerlink" title="带有$\epsilon$边的NFA"></a>带有$\epsilon$边的NFA</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510100652361.png" alt="image-20200510100652361"></p>
<p>带有和不带有”$\epsilon$-边”的 NFA的等价性：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510100741694.png" alt="image-20200510100741694"></p>
<h3 id="DFA算法实现"><a href="#DFA算法实现" class="headerlink" title="DFA算法实现"></a>DFA算法实现</h3><p>NFA比DFA更直观，但是DFA更容易实现。</p>
<p>输入：以文件结束符eof结尾的字符串x，DF的开始状态$s_0$，接受状态F，转换函数move</p>
<p>输出：如果D接受x，则回答“yes”，否则回答“No”</p>
<p>方法：将下述算法应用于输入串x:</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510101135283.png" alt="image-20200510101135283"></p>
<h2 id="从正则表达式到有穷自动机"><a href="#从正则表达式到有穷自动机" class="headerlink" title="从正则表达式到有穷自动机"></a>从正则表达式到有穷自动机</h2><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510101814026.png" alt="image-20200510101814026"></p>
<p>因为NFA比较直观，所以根据RE构建NFA比较容易。</p>
<p>又因为NFA和DFA等价，所以再根据NFA构造DFA。</p>
<p>先将RE转换成NFA，然后再从NFA转成DFA。</p>
<p>根据RE构造NFA:<br><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510104154071.png" alt="image-20200510104154071"></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510104207824.png" alt="image-20200510104207824"></p>
<p>例子：$r=（a|b）^*abb$对应的NFA</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510104259359.png" alt="image-20200510104259359"></p>
<h2 id="从NFA到DFA"><a href="#从NFA到DFA" class="headerlink" title="从NFA到DFA"></a>从NFA到DFA</h2><p>例子：</p>
<p> <img src="C:/Program%20Files/Typora/upload/image-20200510104810148.png" alt="image-20200510104810148"></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510105240112.png" alt="image-20200510105240112"></p>
<h3 id="子集构造法"><a href="#子集构造法" class="headerlink" title="子集构造法"></a>子集构造法</h3><p>输入：NFA<br>输出：接收相同语言的DFA</p>
<p>方法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510114605955.png" alt="image-20200510114605955"></p>
<p><img src="C:/Program%20Files/Typora/upload/image-20200510115300043.png" alt="image-20200510115300043"></p>
<h2 id="识别单词的DFA"><a href="#识别单词的DFA" class="headerlink" title="识别单词的DFA"></a>识别单词的DFA</h2><h3 id="标识符的DFA"><a href="#标识符的DFA" class="headerlink" title="标识符的DFA"></a>标识符的DFA</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510115550338.png" alt="image-20200510115550338"></p>
<h3 id="无符号数的DFA"><a href="#无符号数的DFA" class="headerlink" title="无符号数的DFA"></a>无符号数的DFA</h3><p> <img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510115650316.png" alt="image-20200510115650316"></p>
<p>因为NFA存在空边”$\epsilon $”，所以将NFA转换成DFA：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510120629577.png" alt="image-20200510120629577"></p>
<h3 id="识别各进制无符号整数的DFA"><a href="#识别各进制无符号整数的DFA" class="headerlink" title="识别各进制无符号整数的DFA"></a>识别各进制无符号整数的DFA</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510120727145.png" alt="image-20200510120727145"></p>
<h3 id="识别注释的DFA"><a href="#识别注释的DFA" class="headerlink" title="识别注释的DFA"></a>识别注释的DFA</h3><p><img src="C:/Program%20Files/Typora/upload/image-20200510142715112.png" alt="image-20200510142715112"></p>
<h3 id="识别Token的DFA"><a href="#识别Token的DFA" class="headerlink" title="识别Token的DFA"></a>识别Token的DFA</h3><p>识别各类符号。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510142819794.png" alt="image-20200510142819794"></p>
<h2 id="词法分析阶段的错误处理"><a href="#词法分析阶段的错误处理" class="headerlink" title="词法分析阶段的错误处理"></a>词法分析阶段的错误处理</h2><p>词法分析阶段可检测错误的类型</p>
<ul>
<li>单词拼写错误：int i = 0x3G;</li>
<li>非法字符：~@</li>
</ul>
<p>词法错误检测：如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序。</p>
<p>错误处理：</p>
<ul>
<li>查找已扫描字符串中最后一个车对应于某终态的字符<ul>
<li>如果找到了，将该字符与前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词</li>
<li>如果没找到，则确定出错，采用错误恢复策略</li>
</ul>
</li>
</ul>
<p>错误恢复策略：</p>
<p>最简单的错误恢复策略：<strong>恐慌模式</strong>恢复</p>
<p>从剩余的输入中不断删除字符，直到词法分析器能过在剩余输入的开头发现一个正确的字符为止。</p>
<h1 id="语法分析-1"><a href="#语法分析-1" class="headerlink" title="语法分析"></a>语法分析</h1><h2 id="自顶向下分析概述"><a href="#自顶向下分析概述" class="headerlink" title="自顶向下分析概述"></a>自顶向下分析概述</h2><p>从分析树的顶部(根结点)向底部(叶节点)方向构造分析树。</p>
<p>可以看成是从文法开始符号$S$推导出词串$w$的过程：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510143819079.png" alt="image-20200510143819079"></p>
<p>每一步推导中，都需要做两个选择：</p>
<ul>
<li>替换当前句型中的哪个非终结符</li>
<li>用该非终结符的哪个候选式进行替换</li>
</ul>
<h3 id="最左推导"><a href="#最左推导" class="headerlink" title="最左推导"></a>最左推导</h3><p>在最左推导中，总是选择每个句型的最左非终结符进行替换。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510144156287.png" alt="image-20200510144156287"></p>
<p>如果$S \Rightarrow^*_{lm} \alpha$，则称$\alpha$是当前文法的最左句型。</p>
<h3 id="最右推导"><a href="#最右推导" class="headerlink" title="最右推导"></a>最右推导</h3><p>在最右推导中，总是选择每个句型的最右非终结符进行替换。</p>
<p><img src="C:/Program%20Files/Typora/upload/image-20200510144343503.png" alt="image-20200510144343503"></p>
<p>在自底向上的分析中，总是采用最左规约的方式，因此把最左规约称为规范规约，而最右推导相应地称为规范推导。</p>
<h3 id="最左推导和最右推导的唯一性"><a href="#最左推导和最右推导的唯一性" class="headerlink" title="最左推导和最右推导的唯一性"></a>最左推导和最右推导的唯一性</h3><p>给定分析树，推导可能不是唯一的，因为我们选择中间任意一个非终结符进行替换。但是每棵分析树对应的最左推导和最右推导是唯一的。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510144826925.png" alt="image-20200510144826925"></p>
<h3 id="自动向下的语法分析采用最左推导方法"><a href="#自动向下的语法分析采用最左推导方法" class="headerlink" title="自动向下的语法分析采用最左推导方法"></a>自动向下的语法分析采用最左推导方法</h3><p>由于分析器都是从左到右的扫描字符串，所以自动向下的语法分析采用最左推导的方式。</p>
<ul>
<li>总是选择每个句型的最左非终结符进行替换</li>
<li>根据输入流中的下一个终结符，选择最左非终结符的一个候选式</li>
</ul>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510145052277.png" alt="image-20200510145052277"></p>
<h3 id="自顶向下语法分析的通用形式"><a href="#自顶向下语法分析的通用形式" class="headerlink" title="自顶向下语法分析的通用形式"></a>自顶向下语法分析的通用形式</h3><p>递归下降分析：</p>
<ul>
<li>由一组过程组成，每个过程对应一个非终结符</li>
<li>从文法开始符号$S$对应的过程开始，其中递归调用文法中其他非终结符对应的过程。如果$S$对应的过程体恰好扫面了整个输入串，则更成功完成语法分析。</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510145346504.png" alt="image-20200510145346504"></p>
<p>需要回溯的分析器，称为不确定分析器。</p>
<p>如果在分析的过程中，预测出正确的产生式，就不需要回溯，这种分析叫做预测分析。</p>
<ul>
<li><p>预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数(通常是一个)符号来选择正确的$A$-产生式</p>
</li>
<li><p>可以对某些文法构造出向前看$k$个输入符号的预测分析器，该类文法有时也称为$LL(k)$文法类</p>
</li>
<li><p>预测分析不需要回溯，是一种确定的自顶向下分析方法。</p>
</li>
</ul>
<h2 id="文法转换"><a href="#文法转换" class="headerlink" title="文法转换"></a>文法转换</h2><h3 id="存在的问题"><a href="#存在的问题" class="headerlink" title="存在的问题"></a>存在的问题</h3><ul>
<li>同一非终结符的多个候选式存在相同前缀，将导致回溯现象。</li>
</ul>
<p>比如：$S \Rightarrow aAd | aBe$</p>
<ul>
<li>左递归文法会使递归下降分析器陷入无限循环</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510150629931.png" alt="image-20200510150629931"></p>
<h3 id="消除直接左递归"><a href="#消除直接左递归" class="headerlink" title="消除直接左递归"></a>消除直接左递归</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151001684.png" alt="image-20200510151001684"></p>
<p>$A \rightarrow A\alpha$是一个左递归文法，由于其对应的正则表示为$r= \beta \alpha^*$，所以可以转换成对应的非递归文法：<br>$$<br>A \rightarrow \beta A^\prime  \<br>A^\prime \rightarrow \alpha A^\prime | \epsilon<br>$$<br>事实上，这种消除的过程就是吧左递归转换成了右递归。</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151651151.png" alt="image-20200510151651151"></p>
<p>一般形式：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151633396.png" alt="image-20200510151633396"></p>
<p>消除左递归是要付出代价的——引进一些非终结符和$\epsilon$_产生式</p>
<h3 id="消除间接左递归"><a href="#消除间接左递归" class="headerlink" title="消除间接左递归"></a>消除间接左递归</h3><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510151805416.png" alt="image-20200510151805416"></p>
<p>具体算法：</p>
<p>输入：不含循环推导和$\epsilon-$产生式的文法$G$</p>
<p>输出：等价的无左递归文法</p>
<p>方法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510152057713.png" alt="image-20200510152057713"></p>
<h3 id="提取左公因子"><a href="#提取左公因子" class="headerlink" title="提取左公因子"></a>提取左公因子</h3><p>对于存在公共前缀的产生式：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510152324062.png" alt="image-20200510152324062"></p>
<p>提取左公因子算法：</p>
<p>输入：文法$G$</p>
<p>输出：等价的提取了左公因子的文法</p>
<p>方法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510152409034.png" alt="image-20200510152409034"></p>
<h2 id="LL-1-文法"><a href="#LL-1-文法" class="headerlink" title="LL(1)文法"></a>LL(1)文法</h2><p>递归下降分析，可能遇到回溯，回溯会影响分析器的效率。如果每步可以预测出正确的选择，就不需要回溯，这种分析称为预测分析。</p>
<p>什么样的文法可以采用预测分析呢？就是下面介绍的LL(1)文法。</p>
<h3 id="S-文法"><a href="#S-文法" class="headerlink" title="S_文法"></a>S_文法</h3><p>预测分析发的工作郭广昌：</p>
<ul>
<li>从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符$A$和当前输入符号$\alpha$，选择正确的$A$-产生式。为保证分析的确定性，选出的候选式必须是唯一的。</li>
</ul>
<p>S_文法(简单的确定性文法)满足：</p>
<ul>
<li>每个产生式的右部都以终结符开始</li>
<li>同一非终结符的各个候选式的首终符都不同</li>
</ul>
<p>S_文法中不包含$\epsilon$产生式</p>
<p>例子：对于包含$\epsilon$产生式的文法</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510155556458.png" alt="image-20200510155556458"></p>
<p>什么时候使用$\epsilon$产生式？</p>
<p>如果当前某非终结符$A$与当前的输入符$a$不匹配时，若存在$A \rightarrow \epsilon$，可以通过检查$a$是否可以出现在$A$的后面，来决定是否使用产生式$A \rightarrow \epsilon$。（若文法中无$A \rightarrow \epsilon$，则应报错）。</p>
<h3 id="非终结符的后继符号集"><a href="#非终结符的后继符号集" class="headerlink" title="非终结符的后继符号集"></a>非终结符的后继符号集</h3><p>非终结符$A$的后继符号集</p>
<p>可能在某个句型中紧跟在$A$后边的终结符$a$的集合，记为$FOLLOW(A), FOLLOW(A) = {a|S \Rightarrow^<em> aAa\beta, a \in V_T, a,\beta \in (V_T \cup V_N)^</em> }$</p>
<p>如果$A$是某个句型的最右符号，则将结束符添加到$FOLLOW(A)$中</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200510160542843.png" alt="image-20200510160542843"></p>
<h3 id="产生式可选集"><a href="#产生式可选集" class="headerlink" title="产生式可选集"></a>产生式可选集</h3><p>产生式$A \rightarrow \beta$的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为$SELECT(A \rightarrow \beta)$</p>
<ul>
<li>$SELECT(A \rightarrow \alpha \beta) = {\alpha}$ </li>
<li>$SELECT(A \rightarrow \epsilon) = FOLLOW(A)$</li>
</ul>
<p>q_文法：</p>
<ul>
<li>每个产生式的右部或为$\epsilon$，或以终结符开始</li>
<li>具有相同左部的产生式有不相交的可选集</li>
</ul>
<p>q_文法不含右部以非终结符打头的产生式</p>
<h3 id="串首终结符集"><a href="#串首终结符集" class="headerlink" title="串首终结符集"></a>串首终结符集</h3><p>串首终结符：串首第一个符号，并且是终结符。简称首终结符。</p>
<p>给定一个文法符号串$\alpha$，$\alpha$串首终结符集$FIRST(\alpha)$被定义为可以从$\alpha$推导出的所有串首终结符构成的集合。如果$\alpha \Rightarrow^* \epsilon$，那么$\epsilon$也在$FRRST(\alpha)$中。</p>
<ul>
<li>对于$\forall \alpha \in (V_T \cup V_N)^+, FIRST(\alpha) = {\alpha | \alpha  \Rightarrow \alpha \beta, \alpha \in V_T, \beta \in (V_T \cup V_N)^*}$;</li>
<li>如果$\alpha \Rightarrow \epsilon$，那么$\epsilon \in FIRST(\alpha)$</li>
</ul>
<p>产生式$A \rightarrow  \alpha$的可选集$SELECT$</p>
<ul>
<li>如果$\epsilon \notin FIRST(\alpha)$，那么$SELECT(A \rightarrow \alpha) = FIRST(\alpha)$</li>
<li>如果$\epsilon \in FIRST(\alpha)$，那么$SELECT(A \rightarrow \alpha) = (FIRST(\alpha) - {\epsilon}) \cup FOLLOW(A)$</li>
</ul>
<p>注意：$\Rightarrow ^*$表示通过$n &gt;= 0$步推导；$\Rightarrow ^ +$表示通过$n&gt;0$推导</p>
<h3 id="LL-1-文法-1"><a href="#LL-1-文法-1" class="headerlink" title="LL(1)文法"></a>LL(1)文法</h3><p>文法$G$是$LL(1)$的，当且仅当$G$的任意两个具有相同左部的产生式$A \rightarrow \alpha | \beta$满足下面的条件：</p>
<ul>
<li>如果$\alpha$和$\beta$均不能推导出$\epsilon$，则$FIRST(\alpha) \cup FIRST(\beta) = \Phi$</li>
<li>$\alpha$和$\beta$至多有一个能推导出$\epsilon$</li>
<li>如果$\beta \Rightarrow ^ * \epsilon$，则$FIRST(\alpha) \cup FOLLOW(A) = \Phi$</li>
<li>如果$\alpha \Rightarrow ^ * \epsilon$，则$FIRST(\beta) \cap FOLLOW(A) = \Phi$</li>
</ul>
<p>最后两个条件，可以保证同一非终结符的各个产生式的可选集互不相交。</p>
<p>因此，可以为$LL(1)$文法构造预测分析器。</p>
<p>第一个$L$表示从左向右扫描输入</p>
<p>第二个$L$表示产生最左推导</p>
<p>$1$表示在每一步中只需要向前看一个输入符号来决定语法分析动作</p>
<h2 id="FIRST集和FOLLOW集的计算"><a href="#FIRST集和FOLLOW集的计算" class="headerlink" title="FIRST集和FOLLOW集的计算"></a>FIRST集和FOLLOW集的计算</h2><h3 id="FIRST计算"><a href="#FIRST计算" class="headerlink" title="FIRST计算"></a>FIRST计算</h3><p>$FIRST(X)$：可以从$X$推导出的所有串首终结符所构成的集合。</p>
<p>如果$X \Rightarrow ^* \epsilon$，那么$\epsilon \in FIRST(X)$</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511100600620.png" alt="image-20200511100600620"></p>
<p>算法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511100739781.png" alt="image-20200511100739781"></p>
<p>计算串$X_1 X_2 … X_n$的$FIRST$集合</p>
<p><img src="C:/Program%20Files/Typora/upload/image-20200511101005809.png" alt="image-20200511101005809"></p>
<h3 id="FOLLOW集计算"><a href="#FOLLOW集计算" class="headerlink" title="FOLLOW集计算"></a>FOLLOW集计算</h3><p>$FOLLOW(A)$：可能在某个句型中紧跟在$A$后面的终结符$a$的集合。$FOLLOW(A = {a | S \Rightarrow ^<em> \alpha A \alpha \beta, \alpha \in V_T, \alpha, \beta \in (V_T \cup V_N)^</em>})$</p>
<p>如果$A$是某个句型的最右符号，则将结束符添加到$FOLLOW(a)$中</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511102001166.png" alt="image-20200511102001166"></p>
<p>算法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511102635190.png" alt="image-20200511102635190"></p>
<p>例子：表达式文法各产生式的$SELECT$集</p>
<p>​    <img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511103023304.png" alt="image-20200511103023304"></p>
<p>因为所有具有相同左部的产生式的$SELECT$集不相交，则该表示文法是$LL(1)$文法。</p>
<p>根据$SELECT$集得到的预测分析表：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511104328127.png" alt="image-20200511104328127"></p>
<p>$LL(1)$文法的分析方法：</p>
<ul>
<li>递归的预测分析发</li>
<li>非递归的预测分析法</li>
</ul>
<h3 id="递归预测分析法"><a href="#递归预测分析法" class="headerlink" title="递归预测分析法"></a>递归预测分析法</h3><p>递归的预测分析法是指：在递归下降分析中，编写每一个非终结符对应的过程时，根据预测分析表进行产生式的选择。</p>
<p>根据每个非终结符的产生式和$LL(1)$文法的预测分析表，为每个非终结符编写对应的过程：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511125006810.png" alt="image-20200511125006810"></p>
<h3 id="非递归预测分析法"><a href="#非递归预测分析法" class="headerlink" title="非递归预测分析法"></a>非递归预测分析法</h3><p>非递归的预测分析需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511131205695.png" alt="image-20200511131205695"></p>
<p>例子：</p>
<p>$L={a^n b^n | n &gt;=1}$</p>
<p>首先遇到遇到$a$，直接将$a$压入栈中。直到遇到$b$开始，就从栈中弹出$a$，每来一个$b$就弹出一个$a$，直到栈为空，此时就会满足$a$的个数和$b$的个数相同。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511131651613.png" alt="image-20200511131651613"></p>
<p>首先栈初始化为开始符号，根据栈顶符号和输入符号的开始符号，以及预测分析表，我们将$E$弹出栈，将$TE^ \prime$压入栈中。</p>
<p>然后，栈顶元素为$T$，并且输入开始符号为$id$, 因此将$T$弹出栈，将$FT^\prime$压入栈中。</p>
<p>其次，根据栈顶元素$F$和输入的开始符号为$id$，因此将$F$弹出栈，将$id$压入栈中。</p>
<p>发现栈顶元素和输入的开始符号相等，所以将id淡出栈，并将输入指针向后移动。</p>
<p>一直重复以上步骤。得到上图的右侧分析。</p>
<p>输出的序列就是一个最左推导。</p>
<p><strong>表驱动的预测分析法：</strong></p>
<p>输入：一个串$w$和文法$G$的 分析表$M$</p>
<p>输出：如果$w$在$L(G)$中，输出$w$的最左推导；否则给出错误提示</p>
<p>方法：最初，语法分析器的格局如下：输入缓冲区中是<code>w$</code>，$G$的开始符号位于栈顶，其下面是<code>$</code>。下面的程序使用预测分析表$M$生成了处理这个输入的预测分析过程：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511132902835.png" alt="image-20200511132902835"></p>
<p><strong>递归预测分析法和非递归预测分析法的区别：</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511133109864.png" alt="image-20200511133109864"></p>
<p><strong>预测分析法的实现步骤：</strong></p>
<ul>
<li>构造文法</li>
<li>改造文法：消除二义性，消除左递归，消除回溯</li>
<li>求每个变量的$FIRST$和$SELECT$集，从而求得每个候选式的$sELECT$集</li>
<li>检查是不是$LL(1)$文法，若是，构造预测分析表</li>
<li>对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法。</li>
</ul>
<h3 id="预测分析中的错误检测"><a href="#预测分析中的错误检测" class="headerlink" title="预测分析中的错误检测"></a>预测分析中的错误检测</h3><p>两种情况下可以检测到错误：</p>
<ul>
<li>栈顶的终结符和当前输入符号不匹配</li>
<li>栈顶非终结符娱当前输入符号在预测分析表对应项目的信息为空</li>
</ul>
<p>预测分析中的错误恢复：</p>
<p>恐慌模式：</p>
<ul>
<li>忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元集合中的某个词法单元<ul>
<li>其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复</li>
<li>例如可以把$FOLLOW(A)$中的所有终结符放入非终结符$A$的同步记号集合</li>
</ul>
</li>
<li>如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511143057864.png" alt="image-20200511143057864"></p>
<p>分析表的使用方法：</p>
<ul>
<li>如果$M[A,a]$是空，表示检测到错误，根据恐慌模式，忽略输入符号$a$</li>
<li>如果$M[A, a]$是$synch$，则弹出栈顶的非终结符$A$，试图继续分析后面的语法成分</li>
<li>如果栈顶的终结符和输入符号不匹配，则弹出栈顶的终结符</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511143323782.png" alt="image-20200511143323782"></p>
<h2 id="自底向上分析概述"><a href="#自底向上分析概述" class="headerlink" title="自底向上分析概述"></a>自底向上分析概述</h2><ul>
<li>分析树的底部(叶结点)向顶部(根结点)方向构造分析树</li>
<li>可以看成将输入串$w$规约为文法开始符号$S$的过程</li>
<li>自顶向下的语法分析采用最左推导方式</li>
<li>自底向上的语法分析采用最右规约的方式(反向构造最右推导)</li>
<li>自底向上语法分析的通用看人家<ul>
<li>移入-规约分析</li>
</ul>
</li>
</ul>
<p>例子：移入-规约分析</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511143939647.png" alt="image-20200511143939647"></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511144340728.png" alt="image-20200511144340728"></p>
<p>移入-规约分析的工作过程：</p>
<ul>
<li>对输入串的一次从左到右的扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串$\beta$进行规约为止</li>
<li>然后，它将$\beta$规约为某个产生式的左部</li>
<li>语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空为止。</li>
</ul>
<p>移入-规约分析器可采用的4种动作：</p>
<ul>
<li>移入</li>
<li>规约</li>
<li>接受：宣布语法分析过程成功完成</li>
<li>报错：发现一个语法错误，并调用错误恢复子程序</li>
</ul>
<p>移入-规约分析器存在的问题：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511145557054.png" alt="image-20200511145557054"></p>
<p>上图中的红线，应该被识别为一个整体，并规约为$<ids>$。而上图中却将$i_B$识别为一个字符串，并规约为$<ids>$。</ids></ids></p>
<p>错误的原因：错误地识别了句柄</p>
<p>句柄：句型的最左直接短语</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511145911875.png" alt="image-20200511145911875"></p>
<h2 id="LR分析法概述"><a href="#LR分析法概述" class="headerlink" title="LR分析法概述"></a>LR分析法概述</h2><p>LR文法是最大的、可以构造出相应移入-规约语法分析器的文法类：</p>
<ul>
<li>L：对输入进行从左到右的扫面</li>
<li>R：反向构造出一个最右推导序列</li>
</ul>
<p>$LR(k)$分析：</p>
<p>需要向前查看$k$个输入符号的$LR$分析。</p>
<p>当$k=0$和$k=1$这两种情况具有实践意义，当省略$(k)$时，表示$k=1$</p>
<h3 id="基本原理"><a href="#基本原理" class="headerlink" title="基本原理"></a>基本原理</h3><p>自底向上分析的关键问题是：如何正确识别句柄。</p>
<p>句柄是逐步形成的，用”状态”表示矩形识别exe进展程度。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511152217270.png" alt="image-20200511152217270"></p>
<p>$LR$分析器基于这样一些状态来构造自动机进行句柄识别。</p>
<p>$LR$自动机总体结构：<br><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511152339433.png" alt="image-20200511152339433"></p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511152852447.png" alt="image-20200511152852447"></p>
<h3 id="LR分析器的工作过程"><a href="#LR分析器的工作过程" class="headerlink" title="LR分析器的工作过程"></a>LR分析器的工作过程</h3><p>初始化：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161018159.png" alt="image-20200511161018159"></p>
<p>一般情况下：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161037267.png" alt="image-20200511161037267"></p>
<ul>
<li>如果$ACTION[s_m, a_i] = sx$，那么格局变为：</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161120275.png" alt="image-20200511161120275"></p>
<ul>
<li>如果$ACTION[s_m, a_i] = rx$表示用第$x$个产生式$A \rightarrow X_{m-(k-1)}… X_m$进行规约，那么格局变为：</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161238525.png" alt="image-20200511161238525"></p>
<ul>
<li>如果$GOTO[s_{m-k}, A] = y$，那么格局变为：</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511161331126.png" alt="image-20200511161331126"></p>
<ul>
<li>如果$ACTION[s_m, a_i] = acc$，那么分析成功</li>
<li>如果$ACTION[s_m, a_i] = err$，那么出现语法错误</li>
</ul>
<p>LR分析算法：</p>
<p>输入：串$w$和LR语法分析表，该表描述了文法$G$的ACTION函数和GOTO函数</p>
<p>输出：如果$w$在$L(G)$中，则输出$w$的自底向上语法分析过程中的规约步骤；否则给出一个错误指示</p>
<p>方法：初始时，语法分析器中的内容为初始状态$s_0$，输入缓冲区的内容为：$w$$，然后，语法分析器执行下面的程序：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511153452496.png" alt="image-20200511153452496"></p>
<p>构造$LR$分析表的方法：</p>
<ul>
<li>LR(0)分析</li>
<li>SLR分析</li>
<li>LR(1)分析</li>
<li>LALR分析</li>
</ul>
<h3 id="LR-0-分析"><a href="#LR-0-分析" class="headerlink" title="LR(0)分析"></a>LR(0)分析</h3><p><strong>LR(0)项目</strong>：右部某位置有圆点的产生式称为相应文法的一个$LR(0)$项目（简称项目）<br>$$<br>A \rightarrow a_1 . a_2<br>$$<br><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511162316794.png" alt="image-20200511162316794"></p>
<p><strong>增广文法</strong>：如果$G$是一个以$S$为开始符号的文法，则$G$的增广文法$G ^\prime$就是在$G$中加上新开始符号$S^\prime$和产生式$S^\prime \rightarrow S$而得到的文法。</p>
<p>例如：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511162703912.png" alt="image-20200511162703912"></p>
<p>引入这个新的开始产生式的目的是<strong>使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。</strong></p>
<p>文法中的项目：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511162806324.png" alt="image-20200511162806324"></p>
<p>开始的项目是初始项目，最终的项目是规约项目</p>
<p><strong>后继项目</strong>：同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目。</p>
<p>$A \rightarrow \alpha . X\beta$的后继项目是$A \rightarrow \alpha X .\beta$</p>
<p>每一个项目对应着句柄识别的一个状态，把所有项目作为自动机的状态的话，会导致自动机的状态过于庞大。</p>
<p>那么这些项目中是否存在一些等价的呢？</p>
<p>上面的(0)和(2)等价，(3)(7)和(11)等价，(5)和(13)等价。</p>
<p>当项目中圆点后面是一个非终结符的时候，就存在等价项目。</p>
<p>可以把等价的项目组成一个项目集($I$)，称为项目集闭包，每个项目集闭包对应这自动机的一个状态。</p>
<p>例子：LR(0)自动机</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200511163607090.png" alt="image-20200511163607090"></p>
<p>首先把初始项目放入初始状态($I_0$)中，并且四个构造一个项目集闭包。</p>
<p>然后计算后继项目。状态$I_1$已经是规约状态，所以不会有后继状态。状态$I_2,I_4, I_3$都是中间项目，继续计算后继项目。一直重复直到所有状态到达规约状态。</p>
<p>根据左侧转换图来构造分析表。</p>
<p>sn：n表示状态，即$I$的下标</p>
<p>rm：m表示所用的生成式，即文法中()中的数字</p>
<h3 id="LR-0-分析表构造算法"><a href="#LR-0-分析表构造算法" class="headerlink" title="LR(0)分析表构造算法"></a>LR(0)分析表构造算法</h3><p>CLOSURE()函数：计算给定项目集$I$的闭包</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090031072.png" alt="image-20200512090031072"></p>
<p>GOTO()函数：计算项目集$I$对应文法符号$X$的后继项目集闭包。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090042758.png" alt="image-20200512090042758"></p>
<p>构造$LR(0)$自动机的状态集：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090217925.png" alt="image-20200512090217925"></p>
<p>$LR(0)$分析表构造算法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512090743083.png" alt="image-20200512090743083"></p>
<p>$LR(0)$自动机的形式化定义</p>
<p>文法：$G=(V_N, V_T, P, S)$</p>
<p>$LR(0)$自动机：$M=(C, V_N \cup V_T, GOTO, I_), F$</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091024575.png" alt="image-20200512091024575"></p>
<p>$LR(0)$分析过程中的冲突</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091057805.png" alt="image-20200512091057805"></p>
<p>状态$I_2$存在冲突。$E \rightarrow T.$表示进行规约操作，而$T \rightarrow T . <em> F$表示进行移入操作，将$</em>$移入栈中。所以存在<strong>移入/规约冲突</strong>。</p>
<p>状态$I_9$类似。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091514495.png" alt="image-20200512091514495"></p>
<p>还有一种<strong>规约/归约冲突</strong>。</p>
<p>例子：移入/规约冲突和归约/归约冲突</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091819178.png" alt="image-20200512091819178"></p>
<h3 id="SLR分析"><a href="#SLR分析" class="headerlink" title="SLR分析"></a>SLR分析</h3><p>例子：$LR(0)$分析过程中的冲突</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200512091057805.png" alt="image-20200512091057805"></p>
<p>$LR(0)$没有向前查看符号，没有考虑文法符号的上下文环境。</p>
<p>SLR分析基本思想：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514143755112.png" alt="image-20200514143755112"></p>
<p>也称为$SLR(1)$方法，因为向前查看了一个符号，但是之前提到过如果等于1，可以省略，S表示简单simple，通过$FOLLOW$集就可以解决冲突，后面会讲解有些冲突需要更复杂的方式化简。</p>
<p>开始例子的SLR分析表：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514144217756.png" alt="image-20200514144217756"></p>
<p>SLR分析表构造算法：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514144406272.png" alt="image-20200514144406272"></p>
<p>与$LR(0)$分析算法类似，唯一的不同就是对规约项目的处理上。</p>
<p>如果给定文法的$SLR$分析表中不存在有冲突的动作，那么该文法称为$SLR$文法</p>
<p>$SLR$分析中的冲突：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514144558923.png" alt="image-20200514144558923"></p>
<p>对于状态$I_2$，第一个项目表示，如果下一个符号是$=$，移入动作，将等号移入栈中，进行状态6.</p>
<p>而第二项目表示，遇到$R$的$FOLLOR$集的时候，将栈顶的$L$规约为$R$。</p>
<p>所以遇到等号时，会存在移入\规约冲突。</p>
<h3 id="LR-1-分析"><a href="#LR-1-分析" class="headerlink" title="LR(1)分析"></a>LR(1)分析</h3><p>$SLR$分析存在的问题：</p>
<p>$SLR$只是简单地考察下一个输入符号$b$是否属于与规约项目$A \rightarrow \alpha$相关联的$FOLLOW(A)$，但$b \in FOLLOW(A)$只是规约$\alpha$的一个必要条件，而非充分条件。</p>
<p>对于产生式$A \rightarrow \alpha$的规约，在不同使用位置，$A$会要求不同使用位置，$A$会要求不同的后继符号。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514152143495.png" alt="image-20200514152143495"></p>
<p>在特定位置，$A$的后继符集合是$FOLLOW(A)$的子集。</p>
<p>规范$LR(1)$项目：</p>
<p>将一般形式为$[A \rightarrow \alpha . \beta, a ]$的项称为$LR(1)$项，其中$A \rightarrow \alpha\beta$是一个产生式，$a$是一个终结符（这里将$视为一个特殊的终结符），他表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符。</p>
<ul>
<li>LR(1)中的1指的是项的第二分量的长度</li>
<li>在形如$[A \rightarrow \alpha . \beta, a]$且$\beta \neq \epsilon$的项中，展望符$a$没有任何作用</li>
<li>但是一个形如$[A \rightarrow \alpha ., a]$的项只有在下一个输入符号等于$a$时才能以按照$A \rightarrow \alpha$进行规约<ul>
<li>这样的$a$的集合总是$FOLLOW(A)$的子集，而且他通常是一个真子集</li>
</ul>
</li>
</ul>
<p>LR(1)的等价项目：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514161142318.png" alt="image-20200514161142318"></p>
<p>例子：LR(1)</p>
<p>转换图：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514153425448.png" alt="image-20200514153425448"></p>
<p>分析表：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200514153806088.png" alt="image-20200514153806088"></p>
<p>如果除展望符外，两个$LR(1)$项目集是相同的，则称这两个$LR(a)$项目集是同心的</p>
<h3 id="LALR分析法"><a href="#LALR分析法" class="headerlink" title="LALR分析法"></a>LALR分析法</h3><p>$LR(1)$自动机中存在一些同心项目集，$LR(1)$根据展望符的不同，将原始的$LR(0)$项目进行分裂。这样就使得$LR(1)$中的状态数较$LR(0)$多了很多。比如C语言的语法，$LR(0)$分析表只有几百个状态，而$LR(1)$分析表则有上千个状态。</p>
<p>为了使$LR(1)$技术实用化，就需要需要想办法减少状态数。</p>
<h4 id="LALR-lookahead-LR-分析的基本思想"><a href="#LALR-lookahead-LR-分析的基本思想" class="headerlink" title="LALR(lookahead-LR)分析的基本思想"></a>LALR(lookahead-LR)分析的基本思想</h4><p>寻找具有相同核心的$LR(a)$项集，并将这些项集并为一个项目集。所谓项集的核心就是其第一分量的集合。</p>
<p>然后根据合并后得到的项集族构造语法分析表</p>
<p>如果分析表中没有语法分析动作冲突，给定的文法就称为$LALR(1)$文法，就可以根据该分析表进行语法分析。</p>
<p><strong>合并同心项集：</strong></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518100542173.png" alt="image-20200518100542173"></p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518100655214.png" alt="image-20200518100655214"></p>
<p>合并同心项集时产生规约-规约冲突的例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518100916852.png" alt="image-20200518100916852"></p>
<p>合并同心项集不会产生移进-规约冲突，这是因为合并同心集，实际上合并的是对应项的展望符，而展望符只在规约的时候起作用，对于移进的时候不起作用的。</p>
<p>合并同心项集后，虽然不产生冲突，但可能会推迟错误的发现：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518101430032.png" alt="image-20200518101430032"></p>
<p>状态$I_4$和状态$I_9$是同心的，因此可以合并。</p>
<p>但是如果输入是一个d$，而在会出现错误，只是推迟了两步。</p>
<h4 id="LALR的特点"><a href="#LALR的特点" class="headerlink" title="LALR的特点"></a>LALR的特点</h4><p>形式上与$LR(1)$相同</p>
<p>大小上与$LR(0)$和$SLR$相当的</p>
<p>分析能力介于$SLR$和$LR(1)$二者之间</p>
<p>合并后的展望符集合仍为$FOLLOW$集的子集</p>
<h3 id="二义性文法的LR分析"><a href="#二义性文法的LR分析" class="headerlink" title="二义性文法的LR分析"></a>二义性文法的LR分析</h3><p>二义性文法的特点：</p>
<ul>
<li>每个二义性文法都不是LR的</li>
<li>某些类型的二义性文法在语言的描述和实现中很有用<ul>
<li>二义性文法比非二义性文法更简短，更自然</li>
</ul>
</li>
</ul>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518103311338.png" alt="image-20200518103311338"></p>
<p>应该保守地使用二义性文法，并且必须在严格控制之下使用，因为稍有不慎机会导致语法分析器识别的语言出现偏差。</p>
<h3 id="LR分析中的错误处理"><a href="#LR分析中的错误处理" class="headerlink" title="LR分析中的错误处理"></a>LR分析中的错误处理</h3><p>语法错误的检测：当LR分析器在查询分析表并发现一个报错条目时，就检测到了一个语法错误</p>
<p>错误恢复策略：</p>
<ul>
<li>恐慌模式错误恢复</li>
<li>短语层次错误恢复</li>
</ul>
<p>恐慌模式错误恢复：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518110525787.png" alt="image-20200518110525787"></p>
<p>短语层次错误恢复：</p>
<ul>
<li>检查LR分析表中的每一条报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最右可能引起这个语法错误</li>
<li>然后构造出适当的恢复过程</li>
</ul>
<h1 id="语法制导翻译概述"><a href="#语法制导翻译概述" class="headerlink" title="语法制导翻译概述"></a>语法制导翻译概述</h1><p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518110742089.png" alt="image-20200518110742089"></p>
<p>语法制导翻译的基本思想：</p>
<p>如何表示语义信息？</p>
<p>为CFG的文法符号设置语义属性，用来表示语法成分对应的语义信息。</p>
<p>如何计算语义属性？</p>
<ul>
<li>文法符号的语义属性值是用文法符号所在产生式(语法规则)相关联的语义规则来计算的。</li>
<li>对于给定的输入串x，构造x的语法分析树，并利用与产生式(语法规则)相关联的语义规则来计算分析树中各结点对应的语义属性值</li>
</ul>
<p>将语义规则同语法规则(产生式)联系起来要设计两个概念：</p>
<ul>
<li>语法制导定义(SDD)</li>
<li>语法制导翻译方案(SDT)</li>
</ul>
<p>语法制导定义(SDD):</p>
<p>SDD是对CGF(上下文无关文法)的推广</p>
<ul>
<li>将每个文法符号和一个语义属性集合相关联</li>
<li>将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值</li>
</ul>
<p>如果$X$是一个文法符号，$a$是$X$的一个属性，则用$X.a$表示属性$a$在某个标号为$X$的分析树结点上的值</p>
<p>例如：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518133849440.png" alt="image-20200518133849440"></p>
<p>语法制导翻译方案(SDT)：</p>
<p>SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。按照惯例，语义动作放在花括号内：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200518134001088.png" alt="image-20200518134001088"></p>
<p>一个语义动作在产生式中的位置决定了这个动作的执行时间。</p>
<p>SDD与SDT的区别：</p>
<ul>
<li>SDD<ul>
<li>是关于语言翻译的高层次规格说明</li>
<li>隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序</li>
</ul>
</li>
<li>SDT<ul>
<li>可以看作是对SDD的一种补充，是SDD的具体实施方案</li>
<li>显式地指明了语义规则的计算顺序，以便说明某些实现细节</li>
</ul>
</li>
</ul>
<h2 id="语法制导定义SDD"><a href="#语法制导定义SDD" class="headerlink" title="语法制导定义SDD"></a>语法制导定义SDD</h2><p>文法符号的属性:</p>
<ul>
<li>综合属性</li>
<li>继承属性</li>
</ul>
<h3 id="综合属性"><a href="#综合属性" class="headerlink" title="综合属性"></a>综合属性</h3><p> 在分析树结点N上的非终结符A的综合属性只能通过N的子结点或N本身的属性值来定义。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102004908.png" alt="image-20200521102004908"></p>
<p>终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则。</p>
<h3 id="继承属性"><a href="#继承属性" class="headerlink" title="继承属性"></a>继承属性</h3><p>在分析树结点N上的非终结符A的继承属性只能通过N的父结点，N的兄弟结点或N本身的属性值来定义。</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102350471.png" alt="image-20200521102350471"></p>
<p>终结符没有继承属性。终结符从词法分析器处获得的属性值被归为综合属性值。</p>
<p>例子：带有综合属性的SDD</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102513062.png" alt=""></p>
<p>例子：带有继承属性L.inh的SDD</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521102915480.png" alt="image-20200521102915480"></p>
<p>比如<code>int a, b, c</code>，通过这个分析树，就可以得到<code>a,b,c</code>的类型都为<code>int</code>。</p>
<h3 id="属性文法"><a href="#属性文法" class="headerlink" title="属性文法"></a>属性文法</h3><p>一个没有副作用的SDD有时也称为属性文法。</p>
<p>属性文法的规则仅仅通过其他属性值和常量来定义一个属性值。</p>
<p>例如：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521104402066.png" alt="image-20200521104402066"></p>
<h2 id="SDD的求值顺序"><a href="#SDD的求值顺序" class="headerlink" title="SDD的求值顺序"></a>SDD的求值顺序</h2><p>SDD为CFG中的文法符号设置语义属性。对于给定的输入串x，应用语义规则计算分析树中各结点对应的属性值。</p>
<p>按照什么顺序计算属性值？</p>
<p>语义规则建立了属性之间的依赖关系，在对语法分析树结点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值。</p>
<p>所有属性的依赖关系由<strong>依赖图</strong>描述。</p>
<p><strong>依赖图</strong>：</p>
<ul>
<li>依赖图是一个描述了分析树中结点属性间依赖关系的有向图</li>
<li>分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点</li>
<li>如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边</li>
</ul>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521142101208.png" alt="image-20200521142101208"></p>
<p>综合属性type放在结点的右侧，继承属性in放在结点的左侧。</p>
<p>属性值的计算顺序：</p>
<p>可行的求值顺序是满足下列条件的结点序列$N_1,N_2, …, N_k$：如果依赖图中有一条从结点$N_i$到$N_j$的边($N_i \rightarrow N_j$)，那么$i &lt; j$(即：在结点序列中，$N_i$排在$N_j$前面)。</p>
<p>这样的排序将一个有向图边变成了一个线性排序，这个排序称为这个图的<strong>拓扑排序</strong>。</p>
<p>例子：</p>
<p><img src="https://raw.githubusercontent.com/zxpgo/images/master/img/image-20200521142610030.png" alt="image-20200521142610030"></p>

      
    </div>
    
    
    

    
      <div>
        <div id="wechat_subscriber" style="display: block; padding: 10px 0; margin: 20px auto; width: 100%; text-align: center">
    <img id="wechat_subscriber_qcode" src="/images/wechat-qcode.jpg" alt="zxp wechat" style="width: 200px; max-width: 100%;"/>
    <div>欢迎关注微信公众号！</div>
</div>

      </div>
    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div></div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/WeChatpay.jpg" alt="zxp 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/Alipay.jpg" alt="zxp 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    zxp
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://zxpgo.github.io/2020/04/17/编译原理/" title="编译原理">https://zxpgo.github.io/2020/04/17/编译原理/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tag/编译原理/" rel="tag"># 编译原理</a>
          
        </div>
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2020/04/15/华为笔试-2020-4-15/" rel="next" title="华为笔试-2020.4.15">
                <i class="fa fa-chevron-left"></i> 华为笔试-2020.4.15
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2020/04/20/IO多路复用/" rel="prev" title="IO多路服用">
                IO多路服用 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zODgxNC8xNTM0Mg=="></div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.gif"
                alt="zxp" />
            
              <p class="site-author-name" itemprop="name">zxp</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">176</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">48</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://blog.csdn.net/qq_25774883" target="_blank" title="CSDN">
                      
                        <i class="fa fa-fw fa-globe"></i>CSDN</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/zxpgo/zxpgo" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-globe"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.linkedin.com/feed/" target="_blank" title="LinkedIn">
                      
                        <i class="fa fa-fw fa-globe"></i>LinkedIn</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="1165772354@qq.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-inline">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                友情链接
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="http://theme-next.iissnan.com" title="Next主题" target="_blank">Next主题</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://blog.rexking6.top" title="青爷博客" target="_blank">青爷博客</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://me.csdn.net/download/qq_25774883" title="CSDN下载" target="_blank">CSDN下载</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.livere.com/" title="来必力" target="_blank">来必力</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://tongji.baidu.com/web/welcome/login" title="百度统计" target="_blank">百度统计</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leancloud.cn/" title="LeanCloud" target="_blank">LeanCloud</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://ibruce.info/2015/04/04/busuanzi/" title="不蒜子" target="_blank">不蒜子</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leetcode-cn.com/" title="LeetCode" target="_blank">LeetCode</a>
                  </li>
                
              </ul>
            </div>
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#绪论"><span class="nav-number">1.</span> <span class="nav-text">绪论</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#什么是编译"><span class="nav-number">1.1.</span> <span class="nav-text">什么是编译</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#源文件到目标机器码的过程："><span class="nav-number">1.2.</span> <span class="nav-text">源文件到目标机器码的过程：</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#编译系统结构"><span class="nav-number">1.3.</span> <span class="nav-text">编译系统结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#词法分析"><span class="nav-number">1.3.1.</span> <span class="nav-text">词法分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#语法分析"><span class="nav-number">1.3.2.</span> <span class="nav-text">语法分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#语义分析"><span class="nav-number">1.3.3.</span> <span class="nav-text">语义分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#中间代码生成"><span class="nav-number">1.3.4.</span> <span class="nav-text">中间代码生成</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#目标代码生成"><span class="nav-number">1.3.5.</span> <span class="nav-text">目标代码生成</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#代码优化"><span class="nav-number">1.3.6.</span> <span class="nav-text">代码优化</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#语言及其文法"><span class="nav-number">2.</span> <span class="nav-text">语言及其文法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#基本概念"><span class="nav-number">2.1.</span> <span class="nav-text">基本概念</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#字母表"><span class="nav-number">2.1.1.</span> <span class="nav-text">字母表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#串"><span class="nav-number">2.1.2.</span> <span class="nav-text">串</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#文法定义"><span class="nav-number">2.2.</span> <span class="nav-text">文法定义</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#语言的定义"><span class="nav-number">2.3.</span> <span class="nav-text">语言的定义</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#推导"><span class="nav-number">2.3.1.</span> <span class="nav-text">推导</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#规约"><span class="nav-number">2.3.2.</span> <span class="nav-text">规约</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#句型和句子"><span class="nav-number">2.3.3.</span> <span class="nav-text">句型和句子</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#语言"><span class="nav-number">2.3.4.</span> <span class="nav-text">语言</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#语言上的运算"><span class="nav-number">2.3.5.</span> <span class="nav-text">语言上的运算</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#文法分类"><span class="nav-number">2.4.</span> <span class="nav-text">文法分类</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#CFG-上下文无关文法-的分析树"><span class="nav-number">2.5.</span> <span class="nav-text">CFG(上下文无关文法)的分析树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#分析树是推导的图形化表示"><span class="nav-number">2.5.1.</span> <span class="nav-text">分析树是推导的图形化表示</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#句型的-短语"><span class="nav-number">2.5.2.</span> <span class="nav-text">(句型的)短语</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二义性文法"><span class="nav-number">2.5.3.</span> <span class="nav-text">二义性文法</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#词法分析-1"><span class="nav-number">3.</span> <span class="nav-text">词法分析</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#正则表达式"><span class="nav-number">3.1.</span> <span class="nav-text">正则表达式</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#定义"><span class="nav-number">3.1.1.</span> <span class="nav-text">定义</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#正则语言"><span class="nav-number">3.2.</span> <span class="nav-text">正则语言</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#正则"><span class="nav-number">3.3.</span> <span class="nav-text">正则</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#有穷自动机-FA"><span class="nav-number">3.4.</span> <span class="nav-text">有穷自动机(FA)</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#FA模型"><span class="nav-number">3.4.1.</span> <span class="nav-text">FA模型</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#FA表示"><span class="nav-number">3.4.2.</span> <span class="nav-text">FA表示</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#FA定义-接收-的语言"><span class="nav-number">3.4.3.</span> <span class="nav-text">FA定义(接收)的语言</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最长子串匹配原则"><span class="nav-number">3.4.4.</span> <span class="nav-text">最长子串匹配原则</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#FA分类"><span class="nav-number">3.5.</span> <span class="nav-text">FA分类</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#确定的有穷自动机-DFA"><span class="nav-number">3.5.1.</span> <span class="nav-text">确定的有穷自动机(DFA)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#非确定的有穷自动机-NFA"><span class="nav-number">3.5.2.</span> <span class="nav-text">非确定的有穷自动机(NFA)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#DFS和NFA的等价性"><span class="nav-number">3.5.3.</span> <span class="nav-text">DFS和NFA的等价性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#带有-epsilon-边的NFA"><span class="nav-number">3.5.4.</span> <span class="nav-text">带有$\epsilon$边的NFA</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#DFA算法实现"><span class="nav-number">3.5.5.</span> <span class="nav-text">DFA算法实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#从正则表达式到有穷自动机"><span class="nav-number">3.6.</span> <span class="nav-text">从正则表达式到有穷自动机</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#从NFA到DFA"><span class="nav-number">3.7.</span> <span class="nav-text">从NFA到DFA</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#子集构造法"><span class="nav-number">3.7.1.</span> <span class="nav-text">子集构造法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#识别单词的DFA"><span class="nav-number">3.8.</span> <span class="nav-text">识别单词的DFA</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#标识符的DFA"><span class="nav-number">3.8.1.</span> <span class="nav-text">标识符的DFA</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#无符号数的DFA"><span class="nav-number">3.8.2.</span> <span class="nav-text">无符号数的DFA</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#识别各进制无符号整数的DFA"><span class="nav-number">3.8.3.</span> <span class="nav-text">识别各进制无符号整数的DFA</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#识别注释的DFA"><span class="nav-number">3.8.4.</span> <span class="nav-text">识别注释的DFA</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#识别Token的DFA"><span class="nav-number">3.8.5.</span> <span class="nav-text">识别Token的DFA</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#词法分析阶段的错误处理"><span class="nav-number">3.9.</span> <span class="nav-text">词法分析阶段的错误处理</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#语法分析-1"><span class="nav-number">4.</span> <span class="nav-text">语法分析</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#自顶向下分析概述"><span class="nav-number">4.1.</span> <span class="nav-text">自顶向下分析概述</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#最左推导"><span class="nav-number">4.1.1.</span> <span class="nav-text">最左推导</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最右推导"><span class="nav-number">4.1.2.</span> <span class="nav-text">最右推导</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最左推导和最右推导的唯一性"><span class="nav-number">4.1.3.</span> <span class="nav-text">最左推导和最右推导的唯一性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#自动向下的语法分析采用最左推导方法"><span class="nav-number">4.1.4.</span> <span class="nav-text">自动向下的语法分析采用最左推导方法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#自顶向下语法分析的通用形式"><span class="nav-number">4.1.5.</span> <span class="nav-text">自顶向下语法分析的通用形式</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#文法转换"><span class="nav-number">4.2.</span> <span class="nav-text">文法转换</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#存在的问题"><span class="nav-number">4.2.1.</span> <span class="nav-text">存在的问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#消除直接左递归"><span class="nav-number">4.2.2.</span> <span class="nav-text">消除直接左递归</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#消除间接左递归"><span class="nav-number">4.2.3.</span> <span class="nav-text">消除间接左递归</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#提取左公因子"><span class="nav-number">4.2.4.</span> <span class="nav-text">提取左公因子</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#LL-1-文法"><span class="nav-number">4.3.</span> <span class="nav-text">LL(1)文法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#S-文法"><span class="nav-number">4.3.1.</span> <span class="nav-text">S_文法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#非终结符的后继符号集"><span class="nav-number">4.3.2.</span> <span class="nav-text">非终结符的后继符号集</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#产生式可选集"><span class="nav-number">4.3.3.</span> <span class="nav-text">产生式可选集</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#串首终结符集"><span class="nav-number">4.3.4.</span> <span class="nav-text">串首终结符集</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LL-1-文法-1"><span class="nav-number">4.3.5.</span> <span class="nav-text">LL(1)文法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#FIRST集和FOLLOW集的计算"><span class="nav-number">4.4.</span> <span class="nav-text">FIRST集和FOLLOW集的计算</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#FIRST计算"><span class="nav-number">4.4.1.</span> <span class="nav-text">FIRST计算</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#FOLLOW集计算"><span class="nav-number">4.4.2.</span> <span class="nav-text">FOLLOW集计算</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#递归预测分析法"><span class="nav-number">4.4.3.</span> <span class="nav-text">递归预测分析法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#非递归预测分析法"><span class="nav-number">4.4.4.</span> <span class="nav-text">非递归预测分析法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#预测分析中的错误检测"><span class="nav-number">4.4.5.</span> <span class="nav-text">预测分析中的错误检测</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#自底向上分析概述"><span class="nav-number">4.5.</span> <span class="nav-text">自底向上分析概述</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#LR分析法概述"><span class="nav-number">4.6.</span> <span class="nav-text">LR分析法概述</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本原理"><span class="nav-number">4.6.1.</span> <span class="nav-text">基本原理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LR分析器的工作过程"><span class="nav-number">4.6.2.</span> <span class="nav-text">LR分析器的工作过程</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LR-0-分析"><span class="nav-number">4.6.3.</span> <span class="nav-text">LR(0)分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LR-0-分析表构造算法"><span class="nav-number">4.6.4.</span> <span class="nav-text">LR(0)分析表构造算法</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#SLR分析"><span class="nav-number">4.6.5.</span> <span class="nav-text">SLR分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LR-1-分析"><span class="nav-number">4.6.6.</span> <span class="nav-text">LR(1)分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LALR分析法"><span class="nav-number">4.6.7.</span> <span class="nav-text">LALR分析法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#LALR-lookahead-LR-分析的基本思想"><span class="nav-number">4.6.7.1.</span> <span class="nav-text">LALR(lookahead-LR)分析的基本思想</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#LALR的特点"><span class="nav-number">4.6.7.2.</span> <span class="nav-text">LALR的特点</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二义性文法的LR分析"><span class="nav-number">4.6.8.</span> <span class="nav-text">二义性文法的LR分析</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#LR分析中的错误处理"><span class="nav-number">4.6.9.</span> <span class="nav-text">LR分析中的错误处理</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#语法制导翻译概述"><span class="nav-number">5.</span> <span class="nav-text">语法制导翻译概述</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#语法制导定义SDD"><span class="nav-number">5.1.</span> <span class="nav-text">语法制导定义SDD</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#综合属性"><span class="nav-number">5.1.1.</span> <span class="nav-text">综合属性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#继承属性"><span class="nav-number">5.1.2.</span> <span class="nav-text">继承属性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#属性文法"><span class="nav-number">5.1.3.</span> <span class="nav-text">属性文法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#SDD的求值顺序"><span class="nav-number">5.2.</span> <span class="nav-text">SDD的求值顺序</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div>
<script async src="https//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<i class="fa fa-user-md"></i><span id="busuanzi_container_site_pv" style='display:none'>
    本站总访问量 <span id="busuanzi_value_site_pv"></span> 
    <span class="post-meta-divider">|</span>
</span>
<span id="busuanzi_container_site_uv" style='display:none'>
    访问人数 <span id="busuanzi_value_site_uv"></span>
</span>
</div>


<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<div class="copyright">&copy; 2018-8 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-"></i> Power by 
  </span>
  <span class="author" itemprop="copyrightHolder">zxp</span>
  
  
</div>









        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  




  
  <div id="lv-container" data-uid="MTAyMC8zODgxNC8xNTM0Mg==">
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
	</div>
  











  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            counter.save(null, {
              success: function(counter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.get('time'));
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            var newcounter = new Counter();
            /* Set ACL */
            var acl = new AV.ACL();
            acl.setPublicReadAccess(true);
            acl.setPublicWriteAccess(true);
            newcounter.setACL(acl);
            /* End Set ACL */
            newcounter.set("title", title);
            newcounter.set("url", url);
            newcounter.set("time", 1);
            newcounter.save(null, {
              success: function(newcounter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
              },
              error: function(newcounter, error) {
                console.log('Failed to create');
              }
            });
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "default";
      
          pbOptions.boxForm = "vertical";
      
          pbOptions.position = "top";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
          flOptions.iconStyle = "box";
      
          flOptions.boxForm = "horizontal";
      
          flOptions.position = "middleRight";
      
          flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  
  <script type="text/javascript" src="/js/src/js.cookie.js?v=5.1.4"></script>
  <script type="text/javascript" src="/js/src/scroll-cookie.js?v=5.1.4"></script>


  
  <script type="text/javascript" src="/js/src/exturl.js?v=5.1.4"></script>


  
  
  	 <!-- custom analytics part create by xiamo -->
<script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.1.js"></script>
<script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
<script>
function showTime(Counter) {
	var query = new AV.Query(Counter);
	$(".leancloud_visitors").each(function() {
		var url = $(this).attr("id").trim();
		query.equalTo("url", url);
		query.find({
			success: function(results) {
				if (results.length == 0) {
					var content = $(document.getElementById(url)).text() + ' 0';
					$(document.getElementById(url)).text(content);
					return;
				}
				for (var i = 0; i < results.length; i++) {
					var object = results[i];
					var content = $(document.getElementById(url)).text() + ' ' + object.get('time');
					$(document.getElementById(url)).text(content);
				}
			}
		});

	});
}

</script>
  
</body>
</html>
